public class FindCircleNum {

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        Union union = new Union(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    union.merge(i, j);
                }
            }
        }
        return union.search();
    }

    class Union {
        private final int[] parent;
        public Union(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            while (parent[i] != i) {
                parent[i] = parent[parent[i]];
                i = parent[i];
            }
            return i;
        }

        public void merge(int i, int j) {
            parent[find(i)] = find(j);
        }

        public int search() {
            int ans = 0;
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == i) ++ans;
            }
            return ans;
        }
    }

    boolean[][] flag;
    int[][] isConnected;
    public int findCircleNum1(int[][] isConnected) {
        int n = isConnected.length;
        flag = new boolean[n][n];
        this.isConnected = isConnected;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1 && !flag[i][j]) {
                    dfs(i, j);
                    ++ans;
                }
            }
        }
        return ans;
    }

    public void dfs(int i, int j) {
        flag[i][j] = true;
        for (int k = 0; k < isConnected[0].length; k++) {
            if (isConnected[j][k] == 1 && !flag[j][k]) {
                dfs(j, k);
            }
        }
    }
}
